package com.note.feng.leetcode.algorithms.easy.tree;

public class FiveHundredFortyThree {
    /**
     * 543 二叉树的直径
     * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
     *
     * 示例 :
     * 给定二叉树
     *
     *           1
     *          / \
     *         2   3
     *        / \
     *       4   5
     * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
     *
     * 注意：两结点之间的路径长度是以它们之间边的数目表示。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode.cn/problems/diameter-of-binary-tree
     */
    /**
     * 解法：
     * 二叉树的直径，可以理解为每个节点，左子树的做大深度 + 右子树的最大深度 + 1 （当前节点）的节点数，
     * 满足递归的条件，递归计算出每个节点的节点数，取最大值 - 1（路径 = 节点数 - 1）
     * @param root
     * @return
     */
    int res ;
    public int diameterOfBinaryTree(TreeNode root) {
        res = 1;
        depth(root);
        return res - 1;
    }

    private int depth(TreeNode node){
        if(node == null){
            return 0;
        }
        int left = depth(node.left);
        int right = depth(node.right);
        res = Math.max(res, left + right + 1);
        return Math.max(left, right) + 1;
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
    }
}
